
/*
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.

*/
public class Solution{
	public ListNode removeNthFromEnd(ListNode head, int n) {
		ListNode last,tmp = head;
		int sum = 0;
		while(tmp!=null){
			sum++;
			tmp = tmp.next;
		}
		//System.out.println(sum);
		if(sum==n){
			head = head.next;
			return head;
		}
		int flag = 1;
		tmp = head;
		while(tmp!=null){
			if(flag == (sum-n)){
				last = tmp.next.next;
				tmp.next = last;
				break;
			}
			tmp = tmp.next;
			flag++;
		}
		return head;
	}
	public static void main(String[] args){
		ListNode l1 = new ListNode(4);
		ListNode l2 = new ListNode(2);
		ListNode l3 = new ListNode(7);
		ListNode l4 = new ListNode(1);
		ListNode l5 = new ListNode(3);
		l1.next = l2;
		l2.next = l3;
		l3.next = l4;
		l4.next = l5;
		ListNode result = new Solution().removeNthFromEnd(l1,5);
		while(result != null){
			System.out.print(result.val+" ");
			result = result.next;
		}
	}
}
class ListNode {
	int val;
	ListNode next;
	ListNode(int x) { val = x; }
}